package acwing._1_1AlgorithmBasic._5DynamicProgramming;

/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic._5DynamicProgramming
 * @File : Q0002.java
 * @Author : WangRuoyu
 * @Date : 2023/4/6 9:13
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q0002 {

    /*** 二维数组 ***/
//    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        String[] line = br.readLine().split(" ");
//        final int N = Integer.parseInt(line[0]);
//        final int V = Integer.parseInt(line[1]);
//
//        int[] v = new int[N];
//        int[] w = new int[N];
//
//        for (int i = 0; i < N; i++) {
//            line = br.readLine().split(" ");
//            v[i] = Integer.parseInt(line[0]);
//            w[i] = Integer.parseInt(line[1]);
//        }
//
//        int[][] f = new int[N + 1][V + 1];
//
//        for (int i = 1; i <= N; i++) {
//            for (int j = 0; j <= V; j++) {
//                f[i][j] = f[i - 1][j];
//                if (j >= v[i - 1]) f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i - 1]] + w[i - 1]);
//            }
//        }
//
//        System.out.println(f[N][V]);
//    }

    /*** 一维数组优化 ***/
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        final int N = Integer.parseInt(line[0]);
        final int V = Integer.parseInt(line[1]);

        int[] v = new int[N];
        int[] w = new int[N];

        for (int i = 0; i < N; i++) {
            line = br.readLine().split(" ");
            v[i] = Integer.parseInt(line[0]);
            w[i] = Integer.parseInt(line[1]);
        }

        int[] f = new int[V + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = V; j >= v[i - 1]; j--) {
                f[j] = Math.max(f[j], f[j - v[i - 1]] + w[i - 1]);
            }
        }

        System.out.println(f[V]);
    }
}
